Chịu ảnh hưởng sâu sắc của cha, năm 1916, ông thoát ly gia đình, dạy học ở hai huyện Thanh Chương và Anh Sơn (Nghệ An) mong tìm được bạn cùng chí hướng.[3]

Năm 1919, với bí danh Hồ Tùng Mậu, ông cùng với Lê Hồng Sơn, Ngô Chính Học, Nguyễn Thị Tích, Đặng Quỳnh Anh, dưới sự dẫn đường của Đặng Xuân Thanh, bí mật xuất dương sang Lào rồi sang Xiêm[4]. Sau ba tháng ở Trại Cày ở Bản Đông (tỉnh Phì Chịt), tháng 7 năm 1920, ông cùng Lê Hồng Sơn được cụ Đặng Thúc Hứa bố trí vượt biển sang Quảng Châu (Trung Quốc). Ông ở trọ nhà của chí sĩ Hồ Học Lãm, một họ hàng gần của ông (vai chú), học tiếng Anh, tiếng Trung Quốc, rồi học trường Trung học An Định và trường Bưu điện.[3]

Năm 1923, ông cùng Lê Hồng Sơn, Lê Hồng Phong, Phạm Hồng Thái,… thành lập nhóm Tâm Tâm Xã, một tổ chức thanh niên mang tư tưởng phục quốc, hoạt động chính trị với mục đích giành độc lập cho Việt Nam khỏi chế độ thực dân Pháp. Tháng 3 năm 1924, ông được Phan Bội Châu giao nhiệm vụ mang tài liệu về nước tuyên truyền và vận động thanh niên xuất dương[4], nhưng đến tháng 7 năm 1924, được tin Phạm Hồng Thái mưu sát Toàn quyền Martial Henri Merlin, ông trở lại Quảng Châu.

Tháng 11 năm 1924, Nguyễn Ái Quốc từ Liên Xô về Quảng Châu, tiếp xúc với một số thành viên của Tâm Tâm xã, kết nạp các thành viên này vào tổ chức Cộng sản đoàn. Trong số các thành viên này có Hồ Tùng Mậu và Lê Hồng Sơn.[4]

Hồ Tùng Mậu nhanh chóng trở thành một trong những thành viên tích cực trong việc phát triển Hội. Trong quá trình hoạt động cách mạng, ông còn sử dụng một số bí danh khác như Lương, Ích, Phan Tái, Hồ Mộng Tống, Hồ Quốc Đống, Hồ Tùng Tôn, Ninh Võ, Hà Quị, Yên Chính, Lương Gầy, Lương Tử Anh.[4]

Tháng 6 năm 1925, Nguyễn Ái Quốc thành lập Việt Nam Thanh niên Cách mạng đồng chí Hội trên cơ sở Cộng sản đoàn và mở lớp huấn luyện chính trị cho thanh niên ở trong nước sang. "Ban huấn luyện chính trị đặc biệt" của Hội đặt ở ngôi nhà số 13 đường Văn Minh (Quảng Châu). Hồ Tùng Mậu và Lê Hồng Sơn là giảng viên phụ giảng của Nguyễn Ái Quốc.[4]